package com.cuz.hot100;

import java.util.Stack;

public class Q42catchRain {
    public static void main(String[] args) {
//        int[] ints = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int[] ints = {4, 2, 1, 3, 5};
        System.out.println(monotonicStack(ints));
        System.out.println(dp(ints));
        System.out.println(doublePoint(ints));
    }

    private static int dp(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int len = height.length;
        int[] leftMaxHeight = new int[len];
        int[] rightMaxHeight = new int[len];
        for (int index = 1; index < len; index++) {
            leftMaxHeight[index] = Math.max(height[index - 1], leftMaxHeight[index - 1]);
        }
        for (int index = len - 2; index >= 0; index--) {
            rightMaxHeight[index] = Math.max(rightMaxHeight[index + 1], height[index + 1]);
        }
        int ans = 0;
        for (int index = 0; index < len; index++) {
            int leftHeight = leftMaxHeight[index];
            int rightHeight = rightMaxHeight[index];
            ans += Math.max(0, Math.min(leftHeight, rightHeight) - height[index]);
        }
        return ans;
    }

    public static int monotonicStack(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int ans = 0;
        int len = height.length;
        Stack<Integer> stack = new Stack<>();
        for (int index = 0; index < len; index++) {
            if (stack.isEmpty()) {
                stack.push(index);
                continue;
            }
            //当前柱子可以形成雨水
            while (!stack.isEmpty() && height[index] > height[stack.peek()]) {
                //低洼处的高度
                Integer lowIndex = stack.pop();
                int lowHeight = height[lowIndex];
                //比如 1 2 index=1 pop完之后没有左边界
                if (stack.isEmpty()) {
                    break;
                }
                //4 2 1 3 index=3
                Integer leftMaxIndex = stack.peek(); // 1
                int leftMaxHeight = height[leftMaxIndex];//2
                //距离
                int distance = index - leftMaxIndex - 1;
                ans += (Math.min(leftMaxHeight, height[index]) - lowHeight) * distance;
            }
            // 4 2 1 3 5  index=3 计算就是 4 3 5  把 3放回去避免丢失雨水
            stack.push(index);
        }
        return ans;
    }

    private static int doublePoint(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int leftMax = height[0];
        int len = height.length;
        int rightMax = height[len - 1];
        int left = 0;
        int right = len - 1;
        int ans = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            //左边小于右边
            //3 2 1 4  leftMax=3 left=1 rightMax=4 right= 3
            //左边小于右边表示 left位置以及可以计算了 因为其积水的下限受leftMax限制
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
}
